For propositional logic it can be decided whether a formula has a deduction from a finite set of other formulas. This volume begins with a method to decide this for the quantified formulas of those fragments of arithmetic which express the properties of order-plus-successor and of order-plus-addition (Pressburger arithmetic). It makes use of an algorithm eliminating quantifiers which, in turn, is also applied to obtain consistency proofs for these fragments.

In this volume, logic starts from the observation that in everyday arguments, as brought forward by say a lawyer, statements are transformed linguistically, connecting them in formal ways irrespective of their contents. Understanding such arguments as deductive situations, or "sequents" in the technical terminology, the transformations between them can be expressed as logical rules. The book concludes with the algorithms producing the results of Gentzen's midsequent theorem and Herbrand's theorem for prenex formulas.

In this volume, logic starts from the observation that in everyday arguments, as brought forward say by a lawyer, statements are transformed linguistically, connecting them in formal ways irrespective of their contents. Understanding such arguments as deductive situations, or "sequents" in the technical terminology, the transformations between them can be expressed as logical rules. This leads to Gentzen's calculi of derivations, presented first for positive logic and then, depending on the requirements made on the behaviour of negation, for minimal, intuitionist and classical logic. Identifying interdeducible formulas, each of these calculi gives rise to a lattice-like ordered structure. Describing the generation of filters in these structures leads to corresponding modus ponens calculi, and these turn out to be semantically complete because they express the algorithms generating semantical consequences, as obtained in Volume One of these lectures. The operators transforming derivations from one type of calculus into the other are also studied with respect to changes of the lengths of derivations, and operators eliminating defined predicate and function symbols are described expli

For propositional logic it can be decided whether a formula has a deduction from a finite set of other formulas. The present volume begins with a method to decide this for the quantified formulas of those fragments of arithmetic which express the properties of order-plus-successor and or order-plus-addition (Presburger arithmetic); it makes use of an algorithm eliminating quantifiers which, in turn, is also applied to obtain consistency proofs for these fragments. Stronger fragments of arithmetic, also containing multiplication, are sufficiently rich to express a primitive recursive encoding of terms, formulas and deductions, and this leads to Godel's theorem exhibiting statements already undecidable in these fragments. Its central idea, isolated in Tarski's fixpoint lemma, has a certain analogy with Eubulides' antinomy of the Liar, and in a non-technical chapter, accessible to a wider class of readers, this analogy is exploited for an informal discussion of undefinability and incompleteness. The technical tools required to verify the hypotheses on arithmetical representability, on the other hand, are collected in an independent presentation of recursive functions and relations.

Dieses Lehrbuch behandelt verstandlich, umfassend und modern die Theorie der Berechenbarkeit, ein klassisches Gebiet der Mathematischen Logik, das als Grundlagengebiet auch fur die Informatik von hochster Bedeutung ist. Lebendig und didaktisch klar wird das Studium der berechenbaren Funktionen auf dem Programmbegriff aufgebaut. Dabei sind die Induktion als Beweisprinzip und die Rekursion als Konstruktionsprinzip die beiden grundlegenden Werkzeuge fur den Umgang mit Zahlen und Funktionen. Obwohl uber eine gewisse Vertrautheit mit der mathematischen Argumentationsweise hinaus keine inhaltlichen Kenntnisse aus der Mathematik oder der Informatik vorausgesetzt werden, findet auch der Kenner eine durch viele neuartige Details angereicherte und an neuesten Ergebnissen orientierte Darstellung.